#include <iostream>
#include <cmath>
#include <vector>
using namespace std;
class Solution
{
public:
    vector<int> asteroidCollision(vector<int> &asteroids)
    {
        if (asteroids.size() < 2)
            return asteroids;
        vector<int> rvt;
        vector<int> lvt;
        for (auto &e : asteroids)
        {
            if (e > 0)
            {
                // 向右直接入栈
                rvt.push_back(e);
            }
            else
            {
                // 与向右依次相撞
                bool win = true;
                while (rvt.size())
                {
                    int t = abs(rvt.back());
                    int n = abs(e);
                    // 三种碰撞结果
                    if (n < t)
                    {
                        win = false;
                        break;
                    }
                    else if (n == t)
                    {
                        win = false;
                        rvt.pop_back();
                        break;
                    }
                    else
                    {
                        rvt.pop_back();
                    }
                }
                // 判断是否存活
                if (win)
                    lvt.push_back(e);
            }
        }
        // 最后只剩永远不会相撞的行星
        lvt.insert(lvt.end(), rvt.begin(), rvt.end());
        return lvt;
    }
};